package baseclass.e_tree;


import utils.TreeNode;
import utils.TreeUtil;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 判断是否是完全二叉：
 * 满二叉树：所有叶子在一层，并且第 i层有 2^(i-1)个节点
 * 完全二叉树：
 * case 1:  节点的  左孩子和右孩子都非空，继续
 * case 2:  左孩子为空  右孩子非空，返回false
 * case 3： 左孩子非空， 右孩子为空， 则后面必须开启叶子阶段。
 * case 4： 左右孩子都为空,是叶子阶段
 *
 * @date 2020/2/29 14:39
 */
public class Code09_IsFullBT {
    /**
     * 层次遍历判断
     */
    public static boolean isFullBT(TreeNode head) {
        if (head == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(head);
        //开启叶子阶段
        boolean isLeaf = false;
        while (!queue.isEmpty()) {
            TreeNode root = queue.poll();
            TreeNode left = root.left;
            TreeNode right = root.right;
            if (left != null) queue.offer(left);
            if (right != null) queue.offer(right);
            //case 1
//            if(left != null && right != null) doNothing;
            //case 2
            if (left == null && right != null) return false;

            //case 4
            if (isLeaf && (left != null || right != null)) {
                return false;
            }
            //case 3:注意case3 要在case4后买
            //如果3在4前面，当前root左非空，右空，进入case4  会返回false。
            if (left != null && right == null) {
                isLeaf = true;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode head = new TreeNode(4);
        head.left = new TreeNode(2);
        head.right = new TreeNode(6);
        head.left.left = new TreeNode(1);
//        head.left.left.left = new TreeNode(1);
        head.left.right = new TreeNode(3);
        head.right.left = new TreeNode(5);

        TreeUtil.printTree(head);
        System.out.println(isFullBT(head));

    }
}
